package com.zack.greedy;

import java.util.Arrays;

/**
 * @author zack
 * @create 2019-08-03-16:31
 */

/**
 * 这是2019年8月4号14点的笔记
 * 这个贪心算法并不是最优解，因为在拿的过程中往往会出现别的更优情况
 * 解析：这个算法在进行过程中首先是将性价比高的物件进行排序（在重量上并没有考虑）；
 * 那么在拿的过程中就会出现一个漏洞：比如说
 * 背包可以有20kg的容量
 * 排序好的物品有16kg的钻石（性价比2）   16/32
 * 有10kg的钻石（性价比1.9）             10/19
 * 有10kg的钻石（性价比1.8）             10/18
 */
public class GreedyBag {
    private int MaxWeight = 150;
    private int[] weights = new int[]{35, 30, 60, 50, 40, 10, 25};
    private int[] values = new int[]{10, 40, 30, 50, 35, 40, 30};

    private void BagGreedy(int capacity, int weights[], int values[]) {
        int n = weights.length;
        double[] r = new double[n];
        int index[] = new int[n];//性价比排序物品的下表
        for (int i = 0; i < n; i++) {
            r[i] = (double) values[i] / weights[i];
            index[i] = i;//init
        }
        double temp = 0;//对性价比进行排序(冒泡排序)
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (r[i] < r[j]) {
                    temp = r[i];
                    r[i] = r[j];
                    r[j] = temp;
                    int x = index[i];
                    index[i] = index[j];
                    index[j] = x;
                }
            }
        }
        //将排序好的重量和数组分别放到数组中
        int w1[] = new int[n];
        int v1[] = new int[n];
        for (int i = 0; i < n; i++) {
            w1[i] = weights[index[i]];
            v1[i] = values[index[i]];
        }
        int[] x = new int[n];
        int MaxValues = 0;
        for (int i = 0; i < n; i++) {
            if (w1[i] < capacity) {
                //拿出来物品仍然小于书包
                x[i] = 1; //该物品被拿走了
                capacity -= w1[i];
                MaxValues += v1[i];
                System.out.println("取走的是重量为" + w1[i] + "价值为" + v1[i]);

            }

        }
        System.out.println("背包剩余空间" + capacity);
        //System.out.println("总共拿走的数量是" + Arrays.toString(x));
        System.out.println("总共拿走的价值是" + MaxValues);
    }

    public static void main(String[] args) {
        GreedyBag greedyBag = new GreedyBag();
        greedyBag.BagGreedy(greedyBag.MaxWeight, greedyBag.weights, greedyBag.values);
    }
}
